#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int climbStairs(int n) {
        // if(n == 1)
        //     return 1;
        // if(n == 2)
        //     return 2;
        // return climbStairs(n - 2) + climbStairs(n-1);
        long long p = 1;
        long long q = 2;
        long long r = 3;
        while (--n)
        {
            p = q;
            q = r;
            r = p + q;
        }
        return p;
    }
};